A content addressable memory (CAM) device is a storage device having an array of memory cells that can be instructed to compare the specific pattern of an input string (e.g., a search key or a comparand word) with data stored in rows of the array. The entire CAM array, or segments thereof, may be searched in parallel for a match with the comparand data. If a match exists, the CAM device indicates the match condition by asserting a match flag, and may indicate the existence of multiple matches by asserting a multiple match flag. The CAM device typically includes a priority encoder that logically combines the match results to determine the highest priority matching address (e.g., the lowest matching CAM index). The highest priority matching (HPM) address, the contents of the matched location, and other status information (e.g., skip bit, empty bit, full flag, as well as match and multiple match flags) may be output from the CAM device to an output bus. In addition, associative data may be read out from an associated storage device (e.g., DRAM).
To maximize throughput, the CAM device can be configured to execute a sequence of search operations in a pipelined manner in which the search key of a next search operation is compared with the data stored in the CAM array while the priority encoder is generating the HPM address of a prior search operation. For example, in a search operation for the input string IN1=“abcd” (e.g., which contains a sequence of four binary encoded characters ‘a,’ ‘b,’ ‘c,’ and ‘d’), the first input character “a” is provided as a first search key (SK1) to the CAM array and compared with the CAM data. Then, while the priority encoder uses the match results to generate the HPM address for SK1, the second input character “b” can be provided as a second search key (SK2) and compared with the CAM data. Then, while the priority encoder uses the match results to generate the HPM address for SK2, the third input character “c” can be provided as a third search key (SK3) and compared with the CAM data. Thus, by comparing a subsequent search key with CAM data while the HPM address of a previous search key is generated, device performance is increased over other CAM devices that wait for generation of the HPM address of a prior search key before commencing a subsequent search operation.
To maintain a continuous pipeline operation in the CAM device, the priority encoder is typically configured to generate only the HPM address for each search key. As a result, if there are multiple matching CAM locations for a particular search key, the next highest-priority matching addresses (e.g., the second HPM address, the third HPM address, and so on) are not generated. However, for some applications, it is desirable to generate the addresses of multiple matching locations in the CAM array during search operations. For example, commonly-owned U.S. Pat. No. 6,564,289, which is incorporated by reference herein, discloses a method for performing a read next highest priority match (RNHPM) instruction in a CAM device. More specifically, U.S. Pat. No. 6,564,289 teaches that if a CAM device detects a multiple match condition during a compare operation, the HPM address is generated, and then a separate RNHPM instruction can be sent to the CAM device to cause the next highest priority match address to be generated. During the RNHPM operation, data stored in a column of dedicated multiple match CAM cells is compared with a predetermined logic value in a separate compare operation to generate new match results, which are then provided to the priority encoder to generate the next HPM address. Although able to generate the addresses of multiple matching locations, the CAM device disclosed in U.S. Pat. No. 6,564,289 requires an additional RNHPM instruction and an additional compare operation to generate each next HPM address. In addition, the CAM device described in U.S. Pat. No. 6,564,289 does not disclose processing a sequence of search keys in a pipelined manner, and therefore is silent as to how issuing a series of RNHPM instructions to the CAM device for a first search operation would affect an already initiated but not completed second search operation in the CAM device.
Thus, there is a need for a CAM device that can dynamically output the addresses of multiple matching locations in response to a first search operation with minimal additional latencies and without losing match results for a second search operation that commences prior to generation of multiple matching addresses for the first search operation.
Like reference numerals refer to corresponding parts throughout the drawing figures.